package linkedList;

public class OddEvenLinkedList {
    /*
    * 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
*
* public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
* */

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) {
            return head; // 链表为空或只有一个节点，直接返回
        }

        ListNode oddHead = new ListNode(-1); // 奇数位置链表的虚拟头节点
        ListNode evenHead = new ListNode(-1); // 偶数位置链表的虚拟头节点
        ListNode oddTail = oddHead; // 奇数位置链表的尾节点
        ListNode evenTail = evenHead; // 偶数位置链表的尾节点
        int count = 1;

        ListNode curr = head;
        while (curr != null) {
            if (count % 2 == 1) { // 奇数位置节点
                oddTail.next = curr;
                oddTail = oddTail.next;
            } else { // 偶数位置节点
                evenTail.next = curr;
                evenTail = evenTail.next;
            }
            curr = curr.next;
            count++;
        }

        // 将偶数位置链表连接到奇数位置链表后面
        oddTail.next = evenHead.next;
        // 断开偶数位置链表的尾节点，避免循环
        evenTail.next = null;

        return oddHead.next; // 返回奇数位置链表的头节点
    }

}
